package offer;

import java.util.LinkedList;

public class offerII_0043 {
    class CBTInserter {
        TreeNode node;
        LinkedList<TreeNode> list;
        LinkedList<Integer> num;
        public CBTInserter(TreeNode root) {
            node=root;
            list=new LinkedList<>();
            list.add(root);
            num=new LinkedList<>();
            num.add(0);
            while(true){
                if(list.getFirst().left!=null){
                    num.set(0,1);
                    list.add(list.getFirst().left);
                    num.add(0);
                }
                else{
                    break;
                }
                if(list.getFirst().right!=null){
                    num.removeFirst();
                    list.add(list.getFirst().right);
                    num.add(0);
                    list.removeFirst();
                }
                else break;
            }
        }

        public int insert(int v) {
            int number=num.getFirst();
            TreeNode tmp=new TreeNode(v);
            if(number==0){
                list.getFirst().left=tmp;
                num.set(0,1);
                list.add(tmp);
                num.add(0);
                return list.getFirst().val;
            }
            else{
                list.getFirst().right=tmp;
                list.add(tmp);
                num.add(0);
                TreeNode t=list.removeFirst();
                num.removeFirst();
                return t.val;
            }

        }

        public TreeNode get_root() {
            return node;
        }
    }
}
